package divide_and_conquer;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/o58jfs/
public class LCR_170交易逆序对的总数 {
    class Solution {
        int[] record, tmp;
        public int reversePairs(int[] record) {
            this.record = record;
            tmp = new int[record.length];
            return mergeSort(0, record.length - 1);
        }
        private int mergeSort(int l, int r) {
            // 终止条件
            if (l >= r) return 0;
            // 递归划分
            int m = (l + r) / 2;
            int res = mergeSort(l, m) + mergeSort(m + 1, r);
            // 合并阶段
            int i = l, j = m + 1;
            for (int k = l; k <= r; k++)
                tmp[k] = record[k];
            for (int k = l; k <= r; k++) {
                if (i == m + 1)
                    record[k] = tmp[j++];
                else if (j == r + 1 || tmp[i] <= tmp[j])
                    record[k] = tmp[i++];
                else {
                    record[k] = tmp[j++];
                    res += m - i + 1; // 统计逆序对
                }
            }
            return res;
        }
    }
}
